note:数组内凡是需要交换位置的题目,很容易想到双指针的解法,快慢指针、首尾指针都是常见的应用。
题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。
示例:
1 | 输入:nums = [1,2,3,4] |
提示:
- 0 <= nums.length <= 50000
- 1 <= nums[i] <= 10000
方法一 双指针之快慢指针
思路
常见的快慢指针是行进速度(+1、+2)不同,不过这道题目中快慢指针则是指慢指针有时可以停下来。
这道题归根结底就是让双指针分别指向奇书偶数,如果跑得快的指针指向了奇数,跑的慢的指针指向了偶数,则进行交换。
代码
1 | class Solution { |
复杂度分析
- 时间复杂度$O(n)$。快指针要依次遍历所有的数
- 空间复杂度$O(1)$。没有使用额外空间
方法二 双指针之首尾指针
思路
同理,用两个指针找应该进行互换的元素。
不同的在于,我们让首指针去找第一个偶数,找到后不动,让尾指针去找第一个奇数,找到后进行交换,重复上述操作,直到首尾指针相遇。
代码
1 | class Solution { |
复杂度分析
- 时间复杂度$O(n)$。同理需要首尾指针遍历完所有的数
- 空间复杂度$O(1)$。不需要额外的空间。
原文链接: https://zijian.wang/2021/06/17/21. 调整数组顺序使奇书位于偶数前面/
版权声明: 转载请注明出处.